我们这里贪的是一个能到达的最远范围，我们遍历当前跳跃能到的所有位置，
然后根据该位置上的跳力来预测下一步能跳到的最远距离，贪出一个最远的范围，
一旦当这个范围到达末尾时，当前所用的步数一定是最小步数。
我们需要两个变量cur和pre分别来保存当前的能到达的最远位置和之前能到达的最远位置，
只要cur未达到最后一个位置则循环继续，pre先赋值为cur的值，
表示上一次循环后能到达的最远位置，如果当前位置i小于等于pre，
说明还是在上一跳能到达的范围内，我们根据当前位置加跳力来更新cur，
更新cur的方法是比较当前的cur和i + A[i]之中的较大值，如果题目中未说明是否能到达末尾，
我们还可以判断此时pre和cur是否相等，如果相等说明cur没有更新，即无法到达末尾位置，返回-1
class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0, n = nums.size(), i = 0, cur = 0;
        while (cur < n - 1) {
            ++res;
            int pre = cur;
            for (; i <= pre; ++i) {
                cur = max(cur, i + nums[i]);
            }
            if (pre == cur) return -1; // May not need this
        }
        return res;
    }
};

其实这题最好的解法不是DP，而是贪婪算法Greedy Algorithm，因为我们并不是很关心每一个位置上的剩余步数，
我们只希望知道能否到达末尾，也就是说我们只对最远能到达的位置感兴趣，所以我们维护一个变量reach，
表示最远能到达的位置，初始化为0。遍历数组中每一个数字，如果当前坐标大于reach或者reach已经抵达最后一个位置则跳出循环，
否则就更新reach的值为其和i + nums[i]中的较大值，其中i + nums[i]表示当前位置能到达的最大位置，代码如下：
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size(), reach = 0;
        for (int i = 0; i < n; ++i) {
            if (i > reach || reach >= n - 1) break;
            reach = max(reach, i + nums[i]);
        }
        return reach >= n - 1;
    }
};

这道题说的是有一个非负整数的数组，每个数字表示在当前位置的基础上最多可以走的步数，
求判断能不能到达最后一个位置，开始我以为是必须刚好到达最后一个位置，超过了不算，
其实是理解题意有误，因为每个位置上的数字表示的是最多可以走的步数而不是像玩大富翁一样摇骰子摇出几一定要走几步。
那么我们可以用动态规划Dynamic Programming来解，我们维护一个一位数组dp，
其中dp[i]表示达到i位置时剩余的步数，那么难点就是推导状态转移方程啦。我们想啊，
到达当前位置的剩余步数跟什么有关呢，其实是跟上一个位置的剩余步数和上一个位置的跳力有关，
这里的跳力就是原数组中每个位置的数字，因为其代表了以当前位置为起点能到达的最远位置。
所以当前位置的剩余步数（dp值）和当前位置的跳力中的较大那个数决定了当前能到的最远距离，
而下一个位置的剩余步数（dp值）就等于当前的这个较大值减去1，因为需要花一个跳力到达下一个位置，
所以我们就有状态转移方程了：dp[i] = max(dp[i - 1], nums[i - 1]) - 1，
如果当某一个时刻dp数组的值为负了，说明无法抵达当前位置，则直接返回false，
最后循环结束后直接返回true即可，代码如下：
class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = max(dp[i - 1], nums[i - 1]) - 1;
            if (dp[i] < 0) return false;
        }
        return true;
    }
};